XJOI200814 题解

模拟赛

今天赛 1 是联赛难度。感到自己有很多不足。

赛2：什么叫做乱搞啊 /kk

赛1 赛2

1A

没想出来但这种题有可能会出现在正式赛场上，所以要会乱搞啊！

正解就是选出 K / m 个整行加上 K % m 个在同一行的元素。

有个伪证：

1
2
3
4
5
6
7
8
(a, b, c, d), e, f
(h, i, j), k, l, m

划了括号的是选的。
1. j = e 那么不选 (i, j) 改选 (e, f) 不会更劣
2. j > e 不选 (i, j) 改选 (e, f)
3. j < e 那么 b >= c >= d >= e > j >= k >= l >= m，不选 (b, c, d) 改选 (k, l, m)
所以大概可以说明两行可以合并成一行，即必须取满其中一行。

1B

图论今天真的要刷起来了，这题 lca 搞一搞就好了啊！都忘光了。。。树上路径就是到 lca 的路径啊。。。

那么分两种情况：

  • $lca(c, d)$ 在 $lca(a, b)$ 子树中：发现 $lca(c, d)$ 不在 $a$ 到 $b$ 路径上即可
  • $lca(c, d)$ 不在 $lca(a, b)$ 子树中：$c$ 到 $d$ 的路径不经过连接 $lca(a, b)$ 和 $fa[lca(a, b)]$ 的边即可

于是预处理一波就可以了。

（xj数据水，我一个 $O(n(nq + n^2))$ 的暴力跑过去了。。。。）

1C

神仙构造（noip考构造吗）显然 $S > \frac{n(n - 1)}{2}$ 的时候无解。然后还不会。。咕咕

2A

这很 Atcoder 啊。。神仙构造 + 大乱搞题？咕咕

2B

竟然给我乱搞出来了！考虑操作序列是形如 $(((S + k_1a)b + k_2a)b + k_3a)b + …$ 这样的。我们枚举有几个 $b$（显然只有 log 种），就变成类似于进制，所以要让 $\sum_i k_i$ 最小，只要“能减则减”就可以了。

—-分割线—-

我错了。这题没有一点素质，它的重点根本就是分类讨论，我吐了 思博题💢

!s !t s < t !a !b b = 1 这些你都判了吗

2C

傻了傻了，枚举第一个a、b、c出现的位置就好了呗！这是 $O(n^3)$ 的，然后 $O(n^2)$ 的用树状数组维护就好了（？